package leetcode.sword;

import java.util.*;

public class P32_2 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    LinkedList<TreeNode> pathP = new LinkedList<TreeNode>();
    LinkedList<TreeNode> pathQ = new LinkedList<TreeNode>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        searchP(root,p); //已找到p
        searchQ(root,q); //已找到q
        int i = 0, lenP = pathP.size(), lenQ = pathQ.size();
        while(i<lenP && i<lenQ && pathP.get(i)==pathQ.get(i)){
            i++;
        }
        return pathP.get(i-1);
    }
    public boolean searchP(TreeNode root, TreeNode p){
        if(root==null) return false;
        if(root==p){
            pathP.add(root);
            return true;
        }else{
            pathP.add(root);
        }
        if(searchP(root.left,p)||searchP(root.right,p)){//在root树找到
            return true;
        }else{//root树上没有
            pathP.removeLast(); //删除没用的搜索
            return false;
        }
    }
    public boolean searchQ(TreeNode root, TreeNode p){
        if(root==null) return false;
        if(root==p){
            pathQ.add(root);
            return true;
        }else{
            pathQ.add(root);
        }
        if(searchQ(root.left,p)||searchQ(root.right,p)){//在root树找到
            return true;
        }else{//root树上没有
            pathQ.removeLast(); //删除没用的搜索
            return false;
        }
    }
}
